27. 移除元素

Similar Question

leading to the advanced question

Solution Tips

方案一: 头尾指针

因为题目要求使用原地算法, 把剩余的值都放到头部, 所以很自然的就想到了头尾指针, 头指针一直指向可以存放元素的位置, 尾指针就指向存放废弃元素的位置, 最后返回头指针之前的元素即可

var removeElement = function(nums, val) {
    let left = 0, right = nums.length;
    while (left < right) {
        if (nums[left] === val) {
            nums[left] = nums[right - 1];
            right--;
        } else {
            left++;
        }
    }
    return left;
};

方案二: 快慢指针

参考 26 题的思路, 慢指针永远指向可替换的元素位置, 快指针则快速的去寻找需要替换的元素

var removeElement = function(nums, val) {
        let slow = 0;
        let fast = 0;
        while (slow < nums.length && fast < nums.length) {
			// 需要替换的元素是 != val 的元素
            if (nums[fast] !== val) {
                nums[slow] = nums[fast]
                slow++
            }
            fast++
        }
        return slow;
};

console.log(removeElement([0,1,2,2,3,0,4,2], 2));